#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
using ll = long long;
using T = int;
T rad(); // quick read
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
const int max_size = 5 + 100;
const int maxn = 5 + 1e5;

int num[maxn], siz;
int dp[maxn];

void bfs() {
    queue<int> qe;
    memset(dp, inf, sizeof(dp));
    qe.push(0), dp[0] = 0;
    while (!qe.empty()) {
        int now = qe.front();
        qe.pop();
        for (int i = 1; i <= siz; ++i) {
            int to = now + num[i];
            if (to < maxn && dp[to] == inf) dp[to] = dp[now] + 1, qe.push(to);
            to = now - num[i];
            if (to > 0 && dp[to] == inf) dp[to] = dp[now] + 1, qe.push(to);
        }
    }
}

int main() {
    for (int i = 1; i * i < maxn; ++i) num[++siz] = i * i;
    bfs();
    int Q = rad();
    while (Q--) {
        int x = rad();
        printf("%d\n", dp[x]);
    }
}

T rad() {
    T back = 0;
    int ch = 0, posi = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        posi = ch ^ '-';
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        back = (back << 1) + (back << 3) + (ch & 0xf);
    return posi ? back : -back;
}